r[1<<20]={0,0,1};
main(i,a,n,c,b)
{
	for(c=1,i=3;i<=100000;c+=!b,r[i++]=c)
		for(b=0,a=2;a*a<=i&&!b;a++)
			b|=!(i%a);

	for(gets(&i);~scanf("%d%d",&a,&c);printf("%d\n",r[c]-r[a-1]));
}
